package swardToOffer.struct_4_tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author ChanZany
 * @Date 2021/5/26 10:07
 * @Version 1.0
 * 面试题55（一）：二叉树的深度
 * 题目：输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的
 * 结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
 * 方案1:后序遍历（DFS）
 * 此树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。
 * 终止条件： 当 root​ 为空，说明已越过叶节点，因此返回 深度 0 。
 * 递推工作： 本质上是对树做后序遍历。
 * 1. 计算节点 root​的 左子树的深度 ，即调用 maxDepth(root.left)
 * 2. 计算节点 root​的 右子树的深度 ，即调用 maxDepth(root.right)；
 * 返回值： 返回此树的深度 ，即 max(maxDepth(root.left), maxDepth(root.right)) + 1。
 *
 * 方法2:层序遍历（BFS）每遍历一层，则计数器 +1.直到遍历完成，则可得到树的深度。
 */
public class TreeDepth {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + Math.max(leftDepth,rightDepth);
    }

    public int maxDepth2(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int res = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            Queue<TreeNode> tmp = new LinkedList<>();
            for (TreeNode node : queue) {
                if (node.left != null) tmp.add(node.left);
                if (node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }

    public static void main(String[] args) {
        TreeDepth Main = new TreeDepth();
        TreeNode root = new TreeNode(1);
        TreeNode left1 = new TreeNode(2);
        TreeNode left11 = new TreeNode(3);
        TreeNode left12 = new TreeNode(4);
        TreeNode right = new TreeNode(4);
        root.left = left1;
        root.right = right;
        left1.left=left11;
        left1.right=left12;
        System.out.println(Main.maxDepth(root));
    }
}
